package paixv;

public class Paixv {

	public static void main(String[] args) {
		// int arr[] = new int[1000000];
		// for (int i = 0; i < arr.length; i++) {
		// arr[i] = (int) (Math.random() * 100000);
		// }
		int arr[] = { 42, 20, 17, 13, 28, 14, 23, 15 };
		long start = System.currentTimeMillis();
		bubble(arr);
		// select(arr);
		// insert(arr);
		// quickSort(0, arr.length - 1, arr);
		long end = System.currentTimeMillis();
		System.out.println(end - start);
		// for (int a : arr) {
		// System.out.print(a + " ");
		// }
	}

	public static void bubble(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = 0; j < arr.length - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
			for (int j = 0; j < arr.length; j++) {
				System.out.print(arr[j] + " ");
			}
			System.out.println();
		}
	}

	public static void select(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			int min = arr[i];
			int minIndex = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (min > arr[j]) {
					min = arr[j];
					minIndex = j;
				}
			}
			int temp = arr[i];
			arr[i] = arr[minIndex];
			arr[minIndex] = temp;
		}
	}

	// 3,2,4,6,5
	//
	public static void insert(int[] arr) {
		for (int i = 1; i < arr.length - 1; i++) {
			int insertValue = arr[i];
			int index = i - 1;
			while (index >= 0 && insertValue < arr[index]) {
				arr[index + 1] = arr[index];
				index--;
			}
			arr[index + 1] = insertValue;
			System.out.println(arr.toString());
		}
	}

	public static void quickSort(int left, int right, int[] array) {
		int l = left;
		int r = right;
		int pivot = array[(left + right) / 2];
		int temp = 0;
		while (l < r) {
			while (array[l] < pivot)// 找到一个左边大于中间值的数
				l++;
			while (array[r] > pivot)// 找到右一个边小于中间值的数
				r--;
			if (l >= r)
				break;
			temp = array[l];// 将两数互换
			array[l] = array[r];
			array[r] = temp;
			if (array[l] == pivot)
				--r;
			if (array[r] == pivot)
				++l;
		}
		if (l == r) {
			l++;
			r--;
		}
		if (left < r)
			quickSort(left, r, array);
		if (right > l)
			quickSort(l, right, array);

	}
}
